package practice_once_time;

import java.util.Arrays;

class Item{
    public int Value;//物品价值
    public int weight;//物品重量
    public Item(int weight,int Value){
        this.Value=Value;
        this.weight=weight;
    }
}
public class Knapsack {
    public static double getMaxValue(Item[] items,int capacity){
        //按单位价值比降序排序
        Arrays.sort(items,(item1,item2)->{
            double ratiol1=(double) item1.Value/item1.weight;
            double ratiol2=(double) item2.Value/item2.weight;

            if (ratiol1<ratiol2){
                return -1;
            } else if (ratiol1 > ratiol2) {
                return 1;
            }else {
                return 0;
            }
        });


        double totalValue=0;//总价值
        int currentCapacity=capacity;//剩余背包容量

        for (Item item:items) {
            //如果重量小于剩余容量
            if (item.weight<currentCapacity){
                totalValue+=item.Value;
                currentCapacity-=item.weight;
            }else{//物品部分放入
                double fraction=(double) currentCapacity/item.weight;
                totalValue += item.Value*fraction;
                break;//背包容量不足时只需添加一次部分物品
            }
        }
        return totalValue;
    }

    public static void main(String[] args){
        Item[] items=new Item[]{new Item(10,90),
                new Item(4,40),
                new Item(6,18),
                new Item(3,81),
                new Item(43,96),

        };
        int capacity=20;
        double maxValue=getMaxValue(items,capacity);
        System.out.println("背包的最大价值为"+maxValue);
    }
}
